home *** CD-ROM | disk | FTP | other *** search
/ Complete Linux / Complete Linux.iso / docs / apps / database / postgres / postgre2.z / postgre2 / doc / implementation / planner / 2.pquel < prev    next >
Encoding:
Text File  |  1992-08-27  |  8.6 KB  |  271 lines
  1. .sh 1 "POSTQUEL" 2
  2. .pp
  3. The next two subsections will motivate the different issues that the 
  4. optimizer must consider through several examples.
  5. Then, it will indicate how these new features affect the optimizer. 
  6. .sh 2 "An Extendible Type System"
  7. .pp
  8. One of the features that POSTGRES supports are abstract data types
  9. (ADTs).
  10. An ADT facility allow users to define their own data types,
  11. simplifying representation of complex information.
  12. For example, a user who must store box coordinates in his database
  13. can define a data type called \*(lqboxcoordinates.\*(rq
  14. From here, he can define a relation
  15. BOX with a coordinates field of type \*(lqboxcoordinates.\*(rq
  16. The unit square box shown in figure 2.1, 
  17. therefore, would be represented as shown in figure 2.2.
  18. This is in contrast to figure 2.3.
  19. .(z
  20. .hl
  21. .GS
  22. file figure2.1
  23. .GE
  24. .sp
  25. .ce 2
  26. \fBFigure 2.1\fR
  27. .sp
  28. .sz \n(ep
  29. .TS
  30. center;
  31. |c||c|c|
  32. c||c|c|.
  33. _
  34. BOX    boxid     coordinates
  35. _
  36.     1    ((-1,0), (0,1), (1,0), (0,-1))
  37.     _    _
  38. .TE
  39. .sp
  40. .ce 2
  41. .sz \n(pp
  42. \fBFigure 2.2\fR
  43. Relation with user-defined type \*(lqboxcoordinates\*(rq
  44. .sp 2
  45. .sz \n(ep
  46. .TS
  47. center;
  48. |c||c|c|c|c|c|c|c|c|c|
  49. c||c|c|c|c|c|c|c|c|c|.
  50. _
  51. BOX    boxid    x1    y1    x2    y2    x3    y3    x4    y4
  52. _
  53.     1    -1    0    0    1    1    0    0    -1
  54.     _    _    _    _    _    _    _    _    _
  55. .TE
  56. .sz \n(pp
  57. .sp
  58. .ce 2
  59. \fBFigure 2.3\fR
  60. Relation without user-defined types
  61. .hl
  62. .)z
  63. .pp
  64. POSTGRES also allows users to define operators
  65. to be used in conjunction with user-defined data types.
  66. By defining an operator \*(lqAREA,\*(rq a query to compute the area of the 
  67. above box would be expressed as:
  68. .(l
  69. \fBretrieve\fR (a = AREA(BOX.coordinates)) \fBwhere\fR BOX.boxid = 1
  70. .)l
  71. rather than:
  72. .(l
  73. \fBretrieve\fR (a = sqrt (sqr (BOX.x1 - BOX.x2) + sqr (BOX.y1 - BOX.y2)) +
  74.             sqrt (sqr (BOX.x1 - BOX.x4) + sqr (BOX.y1 - BOX.y4)))
  75.     \fBwhere\fR BOX.boxid = 1.
  76. .)l
  77. .sp
  78. In addition, an operator \*(lqAREAEQ\*(rq (area equals) can be defined
  79. to find all boxes whose area is equal to some desired value.
  80. For example,
  81. .(l
  82. \fBretrieve\fR (BOX.all) \fBwhere\fR BOX.coordinate AREAEQ 10
  83. .)l
  84. finds all boxes whose area equals ten.
  85. Similarly, operators like \*(lqAREALT\*(rq (area less than) and
  86. \*(lqAREAGT\*(rq (area greater than) can also be defined.
  87. .pp
  88. The operators, AREAEQ, AREAGT, and AREALT, are quite similar
  89. to the conventional relational operators, =, >, and <.
  90. Therefore, in the same way that users can specify access methods like
  91. B-trees and hash tables to provide efficient access when used
  92. with conventional operators,
  93. users should also be able to specify access methods to efficiently
  94. scan relations when non-standard operators
  95. appear within restriction clauses.
  96. One solution, which POSTGRES supports, is to allow users to extend 
  97. existing access methods so they can be used with a new set of operators.
  98. For example, by maintaining coordinate records within a B-Tree sorted 
  99. in \*(lqAREALT\*(rq order rather than a more conventional \*(lq<\*(rq
  100. or \*(lq>\*(rq order,
  101. a user has an access method that
  102. provides efficient access to queries whose restrictions contain
  103. the AREAEQ, AREAGT, or AREALT operators.
  104. Another example is a hash table that can be constructed using the operator
  105. \*(lqAREAEQ\*(rq rather than \*(lq=.\*(rq
  106. .pp
  107. The technique just described is suitable provided there exists an
  108. appropriate access method upon which extensions can be made.
  109. However, suppose a user defines an operator contained-in, \*(lq$<<$,\*(rq that
  110. returns true if the left operand is spatially contained within the
  111. right operand.
  112. To provide efficient access to this operator,
  113. two-dimensional access methods are required, e.g.
  114. an R-tree [GUTT84] or a K-D-B Tree [ROBI81].
  115. Since conventional databases do not support two-dimensional access methods,
  116. an extension of an existing access method is not possible.
  117. To alleviate this problem,
  118. POSTGRES allows users to define their own access methods.
  119. Details on user-defined access methods are discussed in [STON86a].
  120. .pp
  121. In summary,
  122. with an extendible type system, users can build data types to suit their
  123. application needs, operators to manipulate the new types, and access methods
  124. to provide efficient access to queries containing these new operators.
  125. .sh 2 "Procedural Data Fields"
  126. .pp
  127. Existing relational databases do not provide good support for storage of
  128. complex objects.
  129. For example, if a complex object consists of a single box, circle, and
  130. triangle, this information would be represented as shown in
  131. figure 2.4.
  132. As a result, three join queries must be executed to
  133. retrieve all information about subobjects within this 
  134. complex object.
  135. .(z
  136. .hl
  137. .sz \n(ep
  138. .in +2.5i
  139. .nf
  140. BOX (bid, bdata)
  141. CIRCLE (cid, cdata)
  142. TRIANGLE (tid, tdata)
  143. .fi
  144. .sp
  145. .in -2.5i
  146. .TS
  147. center;
  148. |c||c|c|c|
  149. c||c|c|c|.
  150. _
  151. COBJECT    coid    objtype    oid
  152. _
  153.     1    box    2
  154.     1    circle    3
  155.     1    triangle    4
  156.     _    _    _
  157. .TE
  158. .sp
  159. .in +2i
  160. .nf
  161. \fBretrieve\fR (BOX.all) \fBwhere\fR
  162.     BOX.bid = COBJECT.oid \fBand\fR
  163.     COBJECT.objtype = \*(lqbox\*(rq \fBand\fR
  164.     COBJECT.coid = 1
  165.  
  166. \fBretrieve\fR (CIRCLE.all) \fBwhere\fR
  167.     CIRCLE.cid = COBJECT.oid \fBand\fR
  168.     COBJECT.objtype = \*(lqcircle\*(rq \fBand\fR
  169.     COBJECT.coid = 1
  170.  
  171. \fBretrieve\fR (TRIANGLE.all) \fBwhere\fR
  172.     TRIANGLE.tid = COBJECT.oid \fBand\fR
  173.     COBJECT.objtype = \*(lqtriangle\*(rq \fBand\fR
  174.     COBJECT.coid = 1
  175. .fi
  176. .in -2i
  177. .sz \n(pp
  178. .sp
  179. .ce 2
  180. \fBFigure 2.4\fR
  181. Storage of complex objects in a relational system
  182. .hl
  183. .)z
  184. In the more general case where a complex object is composed of up to \fIn\fR
  185. different subobject types, a user would have to execute \fIn\fR join queries.
  186. Without extra information indicating which subobject types are actually
  187. contained within a desired object, the user has no choice but to execute all
  188. \fIn\fR queries.
  189. This is quite inefficient, particularly when \fIn\fR is large, because
  190. as indicated in the previous sentence, many of the join queries
  191. are unnecessarily executed.
  192. .pp
  193. The basic problem here is that the relational model is not well-suited for
  194. representing hierarchical relationships.
  195. As a solution, Stonebraker has proposed embedding queries within data
  196. fields and using these queries to express the hierarchical relationship
  197. between the corresponding tuple and information elsewhere in the database
  198. [STON84].
  199. Using this idea, which POSTGRES supports, our complex object example is
  200. now represented as shown in figure 2.5.
  201. .(z
  202. .hl
  203. .sz \n(ep
  204. .TS
  205. center;
  206. |c||c|c|
  207. c||c|l|.
  208. _
  209. COBJECT    coid    components
  210. _
  211.     1    \fBretrieve\fR (BOX.all) \fBwhere\fR BOX.bid = 2
  212.         \fBretrieve\fR (CIRCLE.all) \fBwhere\fR CIRCLE.cid = 3
  213.         \fBretrieve\fR (TRIANGLE.all) \fBwhere\fR TRIANGLE.tid = 4
  214.     _    _
  215. .TE
  216. .sz \n(pp
  217. .sp
  218. .ce 2
  219. \fBFigure 2.5\fR
  220. Storage of complex objects with procedural data fields
  221. .hl
  222. .)z
  223. To retrieve information executed by the queries embedded within this data field,
  224. the user would issue the following query:
  225. .(l
  226. \fBexecute\fR (COBJECT.components) \fBwhere\fR COBJECT.coid = 1.
  227. .)l
  228. Thus, \fIn\fR join queries reduce to a single \fBexecute\fR query.
  229. In addition, users can selectively retrieve information linked through
  230. these hierarchies by nesting attributes in a manner similar to the proposal
  231. in GEM [ZANI83].
  232. For example, to retrieve triangle information for a particular complex object,
  233. a user would nest \*(lqtdata\*(rq within \*(lqcomponents\*(rq as shown below:
  234. .(l
  235. \fBretrieve\fR (COBJECT.components.tdata) \fBwhere\fR COBJECT.coid = 1.
  236. .)l
  237. In general, attributes can be nested to an arbitrary number of levels.
  238. .sh 2 "The POSTGRES Optimizer"
  239. .pp
  240. Query optimization decisions are made based upon the characteristics of
  241. operators appearing within queries as well as the index types defined
  242. on relations.
  243. In a conventional optimizer, information about
  244. operators and access methods can be \*(lqhardwired\*(rq into the
  245. optimization code because there are only a fixed number of
  246. operators and access methods within the system.
  247. Such a solution would not suffice in a system like POSTGRES where
  248. an arbitrary number of operators and access methods are at a
  249. user's disposal.
  250. Consequently, this was an issue that had to be considered when designing the
  251. POSTGRES optimizer.
  252. .pp
  253. The optimizer also must consider queries containing nested attributes.
  254. As section 3.5 will describe, there is a clean and simple solution
  255. to this problem, which only requires that the optimizer apply 
  256. the basic planning algorithm once for each nesting level.
  257. .pp
  258. Rules and triggers will be processed using 
  259. query modification [STON75].
  260. This aspect of POSTGRES will not be discussed in this report because query
  261. modification is being implemented in a module separate from the optimizer.
  262. For details, see [STON86d].
  263. .pp
  264. Sophisticated algorithms have been proposed to optimize transitive closure
  265. queries as well as sets of queries.
  266. This is done by transforming sequences of database operations to
  267. equivalent sequences that execute more efficiently.
  268. This report, however, will not discuss these techniques any further because
  269. the topic is outside the scope of this project.
  270. For details, see [SELL85], [SELL86].
  271.